#pragma once

#include "MasterBinaryTree.hpp"
#include <cctype>
#include <stack>
#include <vector>

typedef int ElemType;

typedef struct BiNode {
    ElemType data;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

class LinkBiTree : public MasterBinaryTree<BiTree, ElemType> {
public:
    Status initBiTree(BiTree& t) override
    {
        t = nullptr;
        return Status::Ok;
    }

    Status destoryBiTree(BiTree& t) override
    {
        if (t == nullptr)
            return Status::Err;

        std::stack<BiTree> nodeStack;
        std::vector<BiTree> deleteList;

        nodeStack.push(t);
        while (!nodeStack.empty()) {
            BiTree current = nodeStack.top();
            nodeStack.pop();

            deleteList.push_back(current);

            if (current->lchild)
                nodeStack.push(current->lchild);
            if (current->rchild)
                nodeStack.push(current->rchild);
        }

        for (auto it = deleteList.rbegin(); it != deleteList.rend(); ++it) {
            delete *it;
        }

        t = nullptr;
        return Status::Ok;
    }

    Status createBiTree(BiTree& t, const std::string& definition) override
    {
        static size_t pos = 0;
        if (pos >= definition.size())
            return Status::Err;

        while (pos < definition.size() && std::isspace(definition[pos])) {
            ++pos;
        }
        if (pos >= definition.size())
            return Status::Err;

        if (definition[pos] == '#') {
            ++pos;
            t = nullptr;
            return Status::Ok;
        }

        int value = 0;
        bool negative = false;

        if (definition[pos] == '-') {
            negative = true;
            ++pos;
        }

        while (pos < definition.size() && std::isdigit(definition[pos])) {
            value = value * 10 + (definition[pos] - '0');
            ++pos;
        }
        if (negative) {
            value = -value;
        }
        t = new BiNode;
        t->data = value;
        t->lchild = t->rchild = nullptr;

        if (createBiTree(t->lchild, definition) != Status::Ok
            || createBiTree(t->rchild, definition) != Status::Ok) {
            destoryBiTree(t);
            return Status::Err;
        }

        return Status::Ok;
    }

    Status clearBiTree(BiTree& t) override
    {
        destoryBiTree(t);
        return initBiTree(t);
    }

    bool biTreeEmpty(const BiTree t) override
    {
        return t == nullptr;
    }

    int biTreeDepth(const BiTree t) override
    {
        if (t == nullptr)
            return Status::Err;
        int left = biTreeDepth(t->lchild);
        int right = biTreeDepth(t->rchild);
        return (left > right ? left : right) + 1;
    }

    BiTree root(const BiTree t) override
    {
        return t;
    }

    ElemType value(const BiTree t, ElemType e) override{

    }
};

